/**
 * 剑指 Offer 16. 数值的整数次方
 * https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
 */
public class Solutions_Offer_16 {
    public static void main(String[] args) {
//        double x = 2.00000;
//        int n = 10;  // output: 1024.00000

        double x = 2.10000;
        int n = 3;  // output: 9.26100

//        double x = 2.00000;
//        int n = -2;  // output: 0.25000

        double result = myPow(x, n);
        System.out.println(result);
    }

    /**
     * 解题思路：快速幂（迭代实现）
     */
    public static double myPow(double x, int n) {
        long b = n;
        if (b < 0) {
            // 2 的 -2 次方 -> 1 / 4 -> 0.25
            // 2 的 -2 次方 -> (1 / 2) 的平方 -> 0.5 * 0.5 -> 0.25
            x = 1 / x;
            b = -b;
        }
        double res = 1.0;

        while (b > 0) {
            if (b % 2 == 1) {
                // 2 的 5 次方 == 2 * (2 的 4 次方)
                res *= x;
            }
            // 2 的 10 次方 == 4(2 * 2) 的 5(10 / 2) 次方
            x *= x;
            b = b / 2;
        }
        return res;
    }
}
